package main

import (
	"container/list"
	"fmt"
)

func main() {
	fmt.Println(isValid("()[]{}"))
}

/**
思路：
1. 使用栈来操作，是左括号就压栈，是右括号的话就判断和栈顶元素是否对应，对应就接着走，直到栈为空，不对应就返回 false
2. 栈可以用单链表实现，因为只对头元素增加和删除
 */
func isValid(s string) bool {
	if len(s) == 0 {
		return true
	}

	var strMap = map[byte]byte{
		']' : '[',
		'}' : '{',
		')' : '(',
	}

	stack := list.New()

	for i := range s {
		front, ok := strMap[s[i]]
		if ok {
			if stack.Len() == 0 {
				return false
			}

			first := stack.Front()
			if front == first.Value{
				stack.Remove(first)
			}else {
				return false
			}
		}else {
			stack.PushFront(s[i])
		}
	}

	return stack.Len() == 0
}
